package com.yaoli.ajob;

import java.util.*;

/**
 * Created by will on 2017/4/24.
 */
public class _127_WordLadder {
    public static void main(String[] args) {
        _127_WordLadder wordLadder = new _127_WordLadder();

        ArrayList<String> set = new ArrayList<>();
        set.add("hot");
        set.add("dot");
        set.add("dog");
        set.add("lot");
        set.add("log");


                //["hot","dot","dog","lot","log"]
//        set.add("hot");
//        set.add("dot");
//        set.add("dog");
//        set.add("lot");
//        set.add("log");
        System.out.println(wordLadder.ladderLength("hit","cog",set));


    }

    /**
     * 此宽度优先遍历不允许存在之前遍历过的值。leetcode 279 可以使用之前遍历过得值。
     *
     * 宽度优先遍历，
     *
     * 使用宽度优先遍历可以不用比较深度，因为如果找到，必然是最短的
     *
     * 类似于树的宽度遍历
     *
     * 使用队列记录每层的结点，记录每层的size
     *
     * 然后判断比较
     * @param beginWord
     * @param endWord
     * @param wordList
     * @return
     */
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {

        HashSet<String> wordSet = new HashSet<>();
        for(int i = 0 ; i < wordList.size() ; i++){
            wordSet.add(wordList.get(i));
        }

        if(!wordSet.contains(endWord)){
            return 0;
        }
        int len = 0;

        Set<String> visited = new HashSet<String>();

        Queue<String> queue = new LinkedList<>();

        visited.add(beginWord);

        queue.add(beginWord);

        boolean flag = false;

        while(queue.size() != 0){

            int levellen = queue.size();

            if(levellen != 0){
                len++;
            }

            while(levellen != 0){
                String word = queue.poll();

                char [] sets = word.toCharArray();

                for(int i = 0 ;i < sets.length;i++){
                    for(char j = 'a' ; j <= 'z' ; j++){
                        char tmpc = sets[i];
                        sets[i] = j;

                        String tmp = String.valueOf(sets);
                        if(tmp.equals(endWord)){
                            flag = true;
                            break;
                        }
                        if(wordSet.contains(tmp) && !visited.contains(tmp)){
                            queue.add(tmp);
                            visited.add(tmp);
                        }
                        sets[i] = tmpc;
                    }
                    if(flag == true){
                        break;
                    }
                }

                if(flag == true){
                    break;
                }

                levellen --;
            }

            if(flag == true){
                break;
            }
        }

        if(flag == true){
            return len+1;
        }else{
            return 0;
        }
    }
    public int ladderLength0(String beginWord, String endWord, Set<String> wordList) {
        Set<String> beginSet = new HashSet<String>(), endSet = new HashSet<String>();

        int len = 1;
        int strLen = beginWord.length();
        HashSet<String> visited = new HashSet<String>();

        beginSet.add(beginWord);
        endSet.add(endWord);
        while (!beginSet.isEmpty() && !endSet.isEmpty()) {
            if (beginSet.size() > endSet.size()) {
                Set<String> set = beginSet;
                beginSet = endSet;
                endSet = set;
            }

            Set<String> temp = new HashSet<String>();
            for (String word : beginSet) {//从单词集合的第一个开
                char[] chs = word.toCharArray();

                for (int i = 0; i < chs.length; i++) { //从单词的第一个字符开始

                    for (char c = 'a'; c <= 'z'; c++) {//从 a字母 到z字母
                        char old = chs[i];
                        chs[i] = c;
                        String target = String.valueOf(chs);

                        if (endSet.contains(target)) {
                            return len + 1;
                        }

                        //没有被访问过 并且 单词列表中有该单词
                        if (!visited.contains(target) && wordList.contains(target)) {
                            temp.add(target);
                            visited.add(target);
                        }
                        chs[i] = old;
                    }
                }
            }

            beginSet = temp;
            len++;
        }

        return 0;
    }


//    At last I'm able to understand. I learned a lot from this solution.
//
//    It's much faster than one-end search indeed as explained in wiki.
//    BFS isn't equivalent to Queue. Sometimes Set is more accurate representation for nodes of level. (also handy since we need to check if we meet from two ends)
//    It's safe to share a visited set for both ends since if they meet same string it terminates early. (vis is useful since we cannot remove word from dict due to bidirectional search)
//    It seems like if(set.add()) is a little slower than if(!contains()) then add() but it's more concise.
//    Thank you all for sharing and explaining!
//
//    update: the dictList is of List type now. And all transformed words including endWord must be in dictList.

    public int ladderLength2(String beginWord, String endWord, Set<String> wordList) {
        Set<String> dict = new HashSet<>(wordList),
                qs = new HashSet<>(),
                qe = new HashSet<>(),
                vis = new HashSet<>();


        qs.add(beginWord);


        if (dict.contains(endWord))
            qe.add(endWord); // all transformed words must be in dict (including endWord)


        //已经包含的开头和结尾 所以是2，
        for (int len = 2; !qs.isEmpty(); len++) {
            Set<String> nq = new HashSet<>();
            for (String w : qs) {
                for (int j = 0; j < w.length(); j++) {
                    char[] ch = w.toCharArray();
                    for (char c = 'a'; c <= 'z'; c++) {
                        if (c == w.charAt(j))
                            continue; // beginWord and endWord not the same, so bypass itself
                        ch[j] = c;
                        String nb = String.valueOf(ch);
                        if (qe.contains(nb))
                            return len; // meet from two ends
                        if (dict.contains(nb) && vis.add(nb))
                            nq.add(nb); // not meet yet, vis is safe to use
                    }
                }
            }
            qs = (nq.size() < qe.size()) ? nq : qe; // switch to small one to traverse from other end
            qe = (qs == nq) ? qe : nq;
        }
        return 0;
    }


    public int ladderLength3(String beginWord, String endWord, Set<String> wordList) {
        int pathLength = 2;

        Set<String> start = new HashSet<>();
        Set<String> end = new HashSet<>();
        start.add(beginWord);
        end.add(endWord);
        wordList.remove(beginWord);
        wordList.remove(endWord);

        while(!start.isEmpty()){
            if(start.size() > end.size()){
                Set<String> temp = start;
                start = end;
                end = temp;
            }
            Set<String> next = new HashSet<>();
            for(String cur : start){
                char[] strArray = cur.toCharArray();
                for(int i = 0; i < strArray.length;i++){
                    char old = strArray[i];
                    for(char c = 'a';c <= 'z';c++){
                        strArray[i] = c;
                        String str = String.valueOf(strArray);
                        if(end.contains(str)){
                            return pathLength;
                        }
                        if(wordList.contains(str)){
                            next.add(str);
                            wordList.remove(str);
                        }
                    }
                    strArray[i] = old;
                }
            }
            start = next;
            pathLength++;
        }
        return 0;
    }
}
